package learnjava.interview;

import java.util.HashMap;

public class Baidu {

    public static void main(String[] args) {

        String s = "0110110";
        int[][] res = m1(s);
        System.out.println(res[0][0]+","+res[0][1]);
        System.out.println(res[1][0]+","+res[1][1]);

    }

    public static int[][] m1(String s){

        //用一个矩阵存储
        int n = s.length();
        int[][][] matrix = new int[n][n][2]; //每一格代表s[i,j]中0和1的个数
        //对角线初始化
        for (int i = 0; i < n; i++) {
            if(s.charAt(i)=='0') matrix[i][i] = new int[]{1,0};
            else matrix[i][i] = new int[]{0,1};
        }
        //其他初始化
        for (int i = 0; i < n; i++) { //按行初始化
            for (int j = i+1; j < n; j++) {
                if(s.charAt(j)=='0'){
                    matrix[i][j][0] = matrix[i][j-1][0]+1;
                    matrix[i][j][1] = matrix[i][j-1][1];
                }else {
                    matrix[i][j][0] = matrix[i][j-1][0];
                    matrix[i][j][1] = matrix[i][j-1][1]+1;
                }
            }
        }
        //按对角线找相等
        for (int k = n-2; k >=0 ; k--) {
            int i = 0, j = k;
            HashMap<String,int[]> record = new HashMap<>();
            while (j<n){
                String ss = matrix[i][j][0]+" "+matrix[i][j][1];
                if(record.containsKey(ss)) { //有了
                    return new int[][]{record.get(ss),new int[]{i,j}};
                }else {
                    record.put(ss,new int[]{i,j});
                }
                i++;j++;
            }
        }
        return new int[2][2];
    }
}
